/**
 * @file heap.h
 * @author xincz
 * @brief 
 * @version 0.1
 * @date 2021-05-27
 * 
 * @copyright Copyright (c) 2021
 * 
 */
#ifndef _HEAP_H_
#define _HEAP_H_

#include <vector>


/**
 * @brief Heap: a priority queue implemented as a heap.
 * 
 */
template<class T, class Compare = std::less<T>>
class Heap {
public:
    Heap();
    Heap(const std::vector<T>& elems);

    T pop();
    T peek() const;
    void push(const T& elem);
    bool empty() const;

private:
    std::vector<T> _elems;    // internal storage, 1-based
    Compare higherPriority;   // defaults to std::less (min-heap)
    size_t root() const;      // returns the index of the root
    size_t leftChild(size_t currIndex) const;
    size_t rightChild(size_t currIndex) const;
    size_t parent(size_t currIndex) const;
    bool hasAChild(size_t currIndex) const;
    size_t maxPriorityChild(size_t currIndex) const;
    void heapifyDown(size_t currIndex);
    void heapifyUp(size_t currIndex);
};


#endif
